1. Field of the Invention
This invention relates to the rendering of graphic images on computer graphic displays more specifically, this invention relates to the rendering of overlapping graphic images on computer graphic displays.
2. Art Background
Although computer graphic displays are two dimensional in nature, it is quite common to display not only one dimensional or two dimensional objects but also three dimensional objects. The third dimension is identified as the depth of the object. Each object or portion of an object are assigned a depth value which indicates how close to the surface of the display that portion of the image is. This depth value, also referred to as the "z" value, is also used to determine what images or portions of images are in front of another when those images overlap in the two dimensional space. For example, if a first polygon has a "z" value of one and a second polygon which is located at the same X,Y coordinates as the first polygon has a "z" value of three, the first polygon will be in front of the second polygon whereby the second polygon is hidden or obscured by the first polygon. Many techniques, particularly time consuming composition equations, have been developed to address the situation of hidden edges and surfaces. See for example Foley, Van Dam, Fundamentals of Interactive Computer Graphics (Addison-Wesley 1984), pages 553 to 572.
The determination of hidden surfaces or edges becomes complex and computationally time intensive when several polygons contribute to the appearance of a single pixel in the final rendering. This introduces classical aliasing problems because the pixel typically represents a single point sample. For example, suppose a blue polygon covers one half of the pixel and a yellow polygon covers the other half. The final pixel should appear green as the blue and yellow contributions to that pixel are blended. Computing the contributions to a pixel becomes very complex when different polygons have different Z values for that pixel. Also, multiple polygons can cover arbitrary portions of a pixel. To compute the final appearance of the pixel all of the sub-pixel coverage and color information for each polygon must be available. For example, suppose there are 16 sub-pixel sample: (0,1,2, . . . 15). One polygon may have a Z value of 5 and cover sub-pixel samples (0,1,2,3,4,5). A second polygon may have a Z value of 8 and cover sub-pixel samples (4,5,6,7,8,9). Furthermore, either polygon may be rendered into the frame buffer first. To produce the correct result, the coverage, Z and color information of the first polygon must be saved until the second is rendered into the frame buffer. This problem extends to as many polygons as there are combinations of Z and coverage values.
In one technique, only one sub-pixel sample is processed at a time and the entire scene is constructed by processing a display list once for each sub-pixel sample. In this way the information is stored in the display list, minimizing storage requirements, but increasing computational requirements. In addition, the scene must be stored in a manner which will allows repetitive processing of the scene. In another method each sub-pixel sample is stored in the frame buffer. However, this greatly increases the memory required for the frame buffer. Furthermore, while the display list need only be processed once, a separate computation is required for each sub-pixel sample.